﻿using System;
using System.Collections.Generic;
using System.Linq;

namespace CompileApp.Models;

public class Parse
{
    private readonly Dictionary<string, List<Production>> _productions = new();

    public readonly Dictionary<string, HashSet<Production>> Significations = new();

    public Dictionary<HashSet<Production>, string> Labels = new(HashSet<Production>.CreateSetComparer());
    private Dictionary<Production, string> _rulesIndex = new();
    public Dictionary<string, Production> Rules = new();
    public Dictionary<string, HashSet<string>> Edges = new();

    public readonly Dictionary<Tuple<string, string>, Status> Action = new();
    public readonly Dictionary<Tuple<string, string>, string> Goto = new();

    public readonly HashSet<string> NonTerminators;
    public readonly HashSet<string> Terminators = new();

    private readonly string _startNode = "";

    public int StateNum = 0;
    public int RuleNum = 0;


    private readonly Dictionary<string, HashSet<string>> _firstSet = new();
    private readonly Dictionary<string, HashSet<string>> _followSet = new();
    private readonly Dictionary<string, bool> _isBlank = new();

    public Parse(string grammar)
    {
        grammar = grammar.Replace(" ", "");
        string[] rules = grammar.Split("\n");

        foreach (var rule in rules)
        {
            if (rule.StartsWith("//"))
            {
                continue;
            }

            string[] parts = rule.Split(new[] { "->", "|" }, StringSplitOptions.RemoveEmptyEntries);

            if (parts.Length <= 1)
            {
                continue;
            }

            if (_startNode.Equals(""))
            {
                _startNode = parts[0];
            }

            if (!_productions.ContainsKey(parts[0]) && parts.Length > 1)
            {
                _productions.Add(parts[0], new List<Production>());
            }

            for (int i = 1; i < parts.Length; i++)
            {
                string[] items = parts[i].Split(new[] { "[", "]" }, StringSplitOptions.RemoveEmptyEntries);
                var item = new Production(parts[0], items.ToList());
                _productions[parts[0]].Add(item);
                _rulesIndex[item] = RuleNum.ToString();
                Rules.Add(RuleNum.ToString(), item);
                RuleNum++;
            }
        }

        var t = new Production("START", new List<string>() { _startNode });
        _productions.Add("START", new List<Production>() { t });
        // _rules_index[t] = RuleNum.ToString();

        NonTerminators = new(_productions.Keys);
        // 初始化所有可以化为空的非终结符
        _init();
        _first();
        // _follow();
        _getResult();
    }


    // 求FIRST集
    private void _first()
    {
        bool flag = true;

        foreach (var nonTerminator in NonTerminators)
        {
            _firstSet.Add(nonTerminator, new HashSet<string>());
            if (_isBlank[nonTerminator])
            {
                _firstSet[nonTerminator].Add("$");
            }
        }

        while (flag)
        {
            flag = false;
            foreach (var nonTerminator in NonTerminators)
            {
                var productions = _productions[nonTerminator];
                foreach (var production in productions)
                {
                    foreach (var item in production.RightItem)
                    {
                        if (NonTerminators.Contains(item))
                        {
                            flag |= !_firstSet[nonTerminator].IsSupersetOf(_firstSet[item]);
                            _firstSet[nonTerminator].UnionWith(_firstSet[item]);
                            if (_isBlank[item])
                            {
                                continue;
                            }
                        }
                        else
                        {
                            flag |= _firstSet[nonTerminator].Add(item);
                        }

                        break;
                    }
                }
            }
        }

        foreach (var nonTerminator in NonTerminators)
        {
            if (!_isBlank[nonTerminator])
            {
                _firstSet[nonTerminator].Remove("$");
            }
        }
    }


    // 求FOLLOW集
    private void _follow()
    {
        foreach (var nonTerminator in NonTerminators)
        {
            _followSet.Add(nonTerminator, new HashSet<string>());
        }

        _followSet[_startNode].Add("#");

        bool flag = true;

        while (flag)
        {
            flag = false;
            foreach (var (key, list) in _productions)
            {
                foreach (var item in list)
                {
                    var rightItem = item.RightItem;
                    for (int i = 0; i < rightItem.Count; i++)
                    {
                        if (!NonTerminators.Contains(rightItem[i]))
                        {
                            continue;
                        }

                        string origin = rightItem[i];

                        if (i == rightItem.Count - 1)
                        {
                            var set = new HashSet<string>(_followSet[key]);
                            set.Remove("$");
                            flag |= !_followSet[origin].IsSupersetOf(set);
                            _followSet[origin].UnionWith(set);
                        }

                        for (int j = i + 1; j < rightItem.Count; j++)
                        {
                            string target = rightItem[j];
                            if (target.Equals("$"))
                            {
                                continue;
                            }

                            if (!NonTerminators.Contains(target))
                            {
                                flag |= _followSet[origin].Add(target);
                            }
                            else
                            {
                                var set = new HashSet<string>(_firstSet[target]);
                                set.Remove("$");
                                flag |= !_followSet[origin].IsSupersetOf(set);
                                _followSet[origin].UnionWith(set);
                            }

                            if (_isBlank.ContainsKey(target))
                            {
                                var set = new HashSet<string>(_followSet[key]);
                                set.Remove("$");
                                flag |= !_followSet[origin].IsSupersetOf(set);
                                _followSet[origin].UnionWith(set);
                            }

                            break;
                        }
                    }
                }
            }
        }
    }


    // 先得到所有非终结符是否可以推到空
    private void _init()
    {
        bool flag = true;
        while (flag)
        {
            flag = false;
            foreach (var nonTerminator in NonTerminators)
            {
                if (_isBlank.ContainsKey(nonTerminator))
                {
                    continue;
                }

                var items = _productions[nonTerminator];
                foreach (var item in items)
                {
                    if (_isBlank.ContainsKey(nonTerminator))
                    {
                        break;
                    }

                    bool t = true;
                    for (int i = 0; i < item.RightItem.Count; i++)
                    {
                        if (item.RightItem[i].Equals("$"))
                        {
                            flag = true;
                            _isBlank.Add(nonTerminator, true);
                            break;
                        }

                        if (_isBlank.ContainsKey(item.RightItem[i]))
                        {
                            continue;
                        }

                        t = false;
                        break;
                    }

                    if (t && !_isBlank.ContainsKey(nonTerminator))
                    {
                        flag = true;
                        _isBlank.Add(nonTerminator, true);
                    }
                }
            }
        }

        foreach (var nonTerminator in NonTerminators)
        {
            if (!_isBlank.ContainsKey(nonTerminator))
            {
                _isBlank.Add(nonTerminator, false);
            }
        }
    }

    // 求预测表
    private void _getResult()
    {
        Production production = new Production("START", new List<string>() { _startNode });
        production.ForwardItem.Add("#");
        var nodes = _closure(new HashSet<Production>() { production });

        var result = _closure(_move(nodes, "S"));

        _addState(nodes);
        HashSet<HashSet<Production>> set = new() { nodes };

        HashSet<string> flags = new();

        while (set.Any())
        {
            flags.Clear();
            var item = set.First();

            foreach (var p in item)
            {
                if (p.Count >= p.RightItem.Count)
                {
                    continue;
                }

                flags.Add(p.RightItem[p.Count]);
                Terminators.Add(p.RightItem[p.Count]);
            }

            // 得到所有
            foreach (var flag in flags)
            {
                var stateIndex = Labels[item];
                var tuple = new Tuple<string, string>(stateIndex, flag);
                var it = _closure(_move(item, flag));
                if (!Labels.ContainsKey(it))
                {
                    _addState(it);
                    set.Add(it);
                }

                if (NonTerminators.Contains(flag))
                {
                    Goto.Add(tuple, Labels[it]);
                }
                else
                {
                    foreach (var production1 in it)
                    {
                        var t = _findType(production1, flag);
                        if (t == ActionType.Not) continue;

                        Action.Add(tuple, new Status(t, Labels[it]));
                        if (!Edges.ContainsKey(stateIndex))
                        {
                            Edges.Add(stateIndex, new HashSet<string>());
                        }
                        Edges[stateIndex].Add(flag);

                        break;
                    }
                }
            }

            set.Remove(item);
        }

        Terminators.ExceptWith(NonTerminators);
        

        foreach (var list in Labels.Keys)
        {
            foreach (var item in list)
            {
                if (item.Count >= item.RightItem.Count)
                {
                    if (item.RightItem[item.Count - 1].Equals(_startNode) && item.RightItem.Count == 1)
                    {
                        foreach (var str in item.ForwardItem)
                        {
                            Action.Add(new Tuple<string, string>(Labels[list], str), new Status(ActionType.Acc));
                            if (!Edges.ContainsKey(Labels[list]))
                            {
                                Edges.Add(Labels[list], new HashSet<string>());
                            }
                            Edges[Labels[list]].Add(str);
                        }
                    }
                    else
                    {
                        foreach (var str in item.ForwardItem)
                        {
                            var tuple = new Tuple<string, string>(Labels[list], str);
                            Action.Add(tuple, new Status(ActionType.R, _rulesIndex[new Production(item)].ToString()));
                            if (!Edges.ContainsKey(Labels[list]))
                            {
                                Edges.Add(Labels[list], new HashSet<string>());
                            }
                            Edges[Labels[list]].Add(str);
                        }
                    }

                    break;
                }
            }
        }
    }

    // 增加一个项目集
    private void _addState(HashSet<Production> nodes)
    {
        Labels.Add(nodes, StateNum.ToString());
        Significations.Add(StateNum.ToString(), nodes);
        StateNum++;
    }

    // LR1项目集规范簇的闭包运算
    private HashSet<Production> _closure(HashSet<Production> origin)
    {
        HashSet<Production> result = new(), target = new(origin);
        Dictionary<Production, HashSet<string>> forwards = new();
        // HashSet<Tuple<string, string>> list = new();

        foreach (var production in origin)
        {
            forwards.Add(new Production(production)
            {
                Count = production.Count
            }, new HashSet<string>(production.ForwardItem));
        }

        while (target.Any())
        {
            var item = target.First();
            // 如果是最后一个符号，或者不是非终结符，就不用继续了
            if (item.Count >= item.RightItem.Count || !NonTerminators.Contains(item.RightItem[item.Count]))
            {
                target.Remove(item);
                continue;
            }

            // 计算前向符号
            var forward = new HashSet<string>();
            if (item.Count < item.RightItem.Count - 1)
            {
                if (NonTerminators.Contains(item.GetCountStr(1)))
                {
                    forward.UnionWith(_firstSet[item.RightItem[item.Count]]);
                }
                else
                {
                    forward.Add(item.GetCountStr(1));
                }
            }
            else
            {
                forward.UnionWith(forwards[new Production(item) { Count = item.Count }]);
            }

            // 如果是非终结符，就把它的所有产生式加入
            var productions = _productions[item.RightItem[item.Count]];
            // 如果是空，就把它的前向符号加入，然后继续
            foreach (var production in productions)
            {
                if (!forwards.ContainsKey(production))
                {
                    forwards.Add(production, new HashSet<string>());
                }

                bool flag = !forwards[production].IsSupersetOf(forward);
                forwards[production].UnionWith(forward);
                if (flag && NonTerminators.Contains(production.RightItem[0]))
                {
                    target.Add(production);
                }
            }

            target.Remove(item);
        }

        foreach (var key in forwards.Keys)
        {
            result.Add(new Production(key)
            {
                Count = key.Count,
                ForwardItem = forwards[key]
            });
        }

        return result;
    }

    // 项目集move一个字符串
    private HashSet<Production> _move(HashSet<Production> origin, string moveStr)
    {
        HashSet<Production> result = new();

        foreach (var production in origin)
        {
            if (production.Count >= production.RightItem.Count ||
                !production.RightItem[production.Count].Equals(moveStr))
            {
                continue;
            }

            var item = new Production(production)
            {
                ForwardItem = production.ForwardItem,
                Count = production.Count + 1
            };

            result.Add(item);
        }


        return result;
    }

    // 判断是否需要添加一个Action表S项
    private ActionType _findType(Production production, string str)
    {
        if (production.Count > 0 && production.RightItem[production.Count - 1].Equals(str))
        {
            return ActionType.S;
        }

        return ActionType.Not;
    }
}

public struct Production
{
    public readonly string LeftItem;
    public readonly List<string> RightItem;
    public HashSet<string> ForwardItem = new();
    public int Count = 0;

    public Production(string leftItem, List<string> rightItem)
    {
        this.LeftItem = leftItem;
        RightItem = rightItem;
    }

    public Production(Production production)
    {
        this.LeftItem = production.LeftItem;
        this.RightItem = production.RightItem;
    }

    public override bool Equals(object? obj)
    {
        if (obj == null || !(obj is Production))
        {
            return false;
        }

        Production other = (Production)obj;
        return this.LeftItem == other.LeftItem &&
               Enumerable.SequenceEqual(this.RightItem, other.RightItem) &&
               this.Count == other.Count &&
               this.ForwardItem.SetEquals(other.ForwardItem);
    }

    public override int GetHashCode()
    {
        int hash = 17;
        hash = hash * 31 + this.LeftItem.GetHashCode();
        foreach (string item in this.RightItem)
        {
            hash = hash * 31 + item.GetHashCode();
        }

        hash = hash * 31 + this.Count.GetHashCode();
        foreach (string item in this.ForwardItem)
        {
            hash = hash * 31 + item.GetHashCode();
        }

        return hash;
    }

    public string GetCountStr(int index = 0)
    {
        return RightItem[Count + index];
    }
}

public struct Status
{
    public string State = "-1";
    public ActionType GType = ActionType.Not;

    public Status(ActionType type, string state = "-1")
    {
        State = state;

        GType = type;
    }
}

public enum ActionType
{
    Acc,
    R,
    S,
    Not
}